package 算法;

import java.util.Arrays;

public class SorUtils {


    /**
     * 冒泡排序
     *
     * @param data
     */
    public static void sortOne(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = 0; j < data.length - 1; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 冒泡排序
     *
     * @param data
     */
    public static void sortTwo(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            //判断第二层循环中的调换有没有执行,如果没有进行两两调换,说明后面都已经排好序了,已经不需要再循环了,直接跳出循环,排序结束.
            boolean flag = true;
            //第二层循环不再循环到arr.length - 1,因为外面的i循环递增一次,说明数组最后就多了一个排好序的大泡泡.第二层循环也就不需要到最末尾一位了,可以提前结束循环
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    // 改变flag
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }


    /**
     * 选择排序也是一种简单直观的排序算法，实现原理比较直观易懂：
     * 首先在未排序数列中找到最小元素，然后将其与数列的首部元素进行交换，然后，在剩余未排序元素中继续找出最小元素，
     * 将其与已排序数列的末尾位置元素交换。以此类推，直至所有元素圴排序完毕.
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i; // 遍历的区间最小的值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 找到当前遍历区间最小的值的索引
                    min = j;
                }
            }
            if (min != i) {
                // 发生了调换
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }

    /**
     * 插入排序 将当前元素和左边的元素比较，若当前元素小，就交换两者，也就相当于插入
     *
     * @param arr
     * @return
     */
    public int[] insertionSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            // j表示当前元素的位置，将其和左边的元素比较，若当前元素小，就交换，也就相当于插入
            // 这样当前元素位于j-1处，j--来更新当前元素,j一直左移不能越界，因此应该大于0
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                int temp = arr[j];        // 元素交换
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
        return arr;
    }

    /**
     * 将数组的某一段元素进行划分，小的在左边，大的在右边
     */
    public static int divide(int[] a, int start, int end) {
        //每次都以最右边的元素作为基准值
        int base = a[end];
        //start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。
        while (start < end) {
            while (start < end && a[start] <= base)
                //从左边开始遍历，如果比基准值小，就继续向右走
                start++;
            //上面的while循环结束时，就说明当前的a[start]的值比基准值大，应与基准值进行交换
            if (start < end) {
                //交换
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
                //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值右边)，因此右边也要同时向前移动一位
                end--;
            }
            while (start < end && a[end] >= base)
                //从右边开始遍历，如果比基准值大，就继续向左走
                end--;
            //上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换
            if (start < end) {
                //交换
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
                //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位
                start++;
            }

        }
        //这里返回start或者end皆可，此时的start和end都为基准值所在的位置
        return end;
    }

    /**
     * 快速排序
     */
    public static void sort(int[] a, int start, int end) {
        if (start > end) {
            //如果只有一个元素，就不用再排下去了
            return;
        } else {
            //如果不止一个元素，继续划分两边递归排序下去
            int partition = divide(a, start, end);
            sort(a, start, partition - 1);
            sort(a, partition + 1, end);
        }
    }


    public static void main(String[] args) {
        int[] data = {4, 1, 3, 6, 2, 5};
//        sortOne(data);
        sort(data);
        Arrays.stream(data).forEach(i -> System.out.println(i));
    }


}
